class Solution:
	# @param {string} s1
	# @param {string} s2
	# @return {boolean}
	def isScramble(self, s1, s2):
		footprint = dict()
		return self.f(s1, s2, footprint)

	def f(self, s1, s2, foot):
		if (s1, s2) in foot:
			return foot[(s1, s2)]
		if len(s1) <= 1:
			return s1 == s2
		if sorted(s1) != sorted(s2):
			return False
		for t in range(1, len(s1)):
			if self.f(s1[:t], s2[:t], foot) and self.f(s1[t:], s2[t:], foot) or \
					self.f(s1[:t], s2[-t:], foot) and self.f(s1[t:], s2[:-t], foot):
				foot[(s1, s2)] = True
				return True
		foot[(s1, s2)] = False
		return False

if __name__ == '__main__':
	print Solution().isScramble('ab','ba')

